package com.study.sort;

public class MergeSort extends Sort {
    @Override
    protected String sortName() {
        return "Merge Sort";
    }

    @Override
    protected void sort(int[] list) {
//        int[] result = mergeSort(list, 0, list.length - 1);
//        System.arraycopy(result, 0, list, 0, result.length);
        ms(list, 0, list.length - 1, new int[list.length]);
    }


    private void ms(int[] list, int l, int r, int[] temp) {
        if (l >= r) {
            return;
        }
        int m = (l + r) / 2;
        ms(list, l, m, temp);
        ms(list, m + 1, r, temp);
        merge(list, l, m, r, temp);
    }

    private void merge(int[] list, int l, int m, int r, int[] temp) {
        int il = l;
        int ir = m + 1;
        int i = l;

        while (il <= m && ir <= r) {
            if (list[il] <= list[ir]) {
                temp[i++] = list[il++];
            } else {
                temp[i++] = list[ir++];
            }
        }

        while (il <= m) {
            temp[i++] = list[il++];
        }

        while (ir <= r) {
            temp[i++] = list[ir++];
        }

        for (int j = l; j <= r; j++) {
            list[j] = temp[j];
        }
    }

    // 0 1 2 3 4 5
    //     2
    // 0,2   3,5
    //  1      4
    // 0,1 2,2   3,4 5,5
    //  0
    //0,0 1,1
    // 0    1
    // 01


    private int[] mergeSort(int[] list, int l, int r) {
        if (l >= r) {
            return new int[]{list[l]};
        }
        int mid = (l + r) / 2;
        int[] left = mergeSort(list, l, mid);

        int[] right = null;
        if (mid + 1 <= r) {
            right = mergeSort(list, mid + 1, r);
        }

        return merge(left, right);
    }

    private int[] merge(int[] left, int[] right) {
        if (right == null) {
            return left;
        }

        int[] result = new int[left.length + right.length];

        int l = 0, r = 0, i = 0;

        while (l < left.length && r < right.length) {
            if (left[l] > right[r]) {
                result[i] = right[r];
                r++;
            } else {
                result[i] = left[l];
                l++;
            }
            i++;
        }

        if (l >= left.length - 1) {
            while (r < right.length) {
                result[i] = right[r];
                r++;
                i++;
            }
        }
        if (r >= right.length - 1) {
            while (l < left.length) {
                result[i] = left[l];
                l++;
                i++;
            }
        }
        return result;
    }
}
